class Solution:
    def search(self, nums: List[int], target: int) -> int:
        length = len(nums)
        index = int(length/2)
        left = 0 # 1 2 3 4 5 6 7
        right = length-1
        while left < right:
            if nums[index] > target:
                right = index-1
                index = int((left+right)/2)
                continue
            elif nums[index] < target:
                left = index+1
                index = int((left+right)/2)
            else:
                return index
        else:
            if left == right:
                if nums[left] == target:
                    return left
            return -1